package com.jhxy.algorithm.maxprofit;

/**
 * 买卖股票最佳时机：动态规划
 */
public class DpSolution {


    public int maxProfit(int[] prices) {
        //买入价格数组
        int[] buyIn = new int[prices.length];
        //卖出价格数组
        int[] saleOut = new int[prices.length];

        //初始化买入和卖出价格
        buyIn[0] = prices[0];
        saleOut[0] = 0;

        for (int i = 1; i < prices.length; i++) {
            saleOut[i] = Math.max(prices[i] - buyIn[i - 1], saleOut[i - 1]);
            buyIn[i] = Math.min(buyIn[i - 1], prices[i]);
        }

        return saleOut[prices.length - 1];
    }
}